{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Kth Largest XOR Coordinate Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #divide-and-conquer #matrix #prefix-sum #quickselect #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #分治 #矩阵 #前缀和 #快速选择 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthLargestValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出第 K 大的异或坐标值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维矩阵 <code>matrix</code> 和一个整数 <code>k</code> ，矩阵大小为 <code>m x n</code> 由非负整数组成。</p>\n",
    "\n",
    "<p>矩阵中坐标 <code>(a, b)</code> 的 <strong>值</strong> 可由对所有满足 <code>0 &lt;= i &lt;= a &lt; m</code> 且 <code>0 &lt;= j &lt;= b &lt; n</code> 的元素 <code>matrix[i][j]</code>（<strong>下标从 0 开始计数</strong>）执行异或运算得到。</p>\n",
    "\n",
    "<p>请你找出 <code>matrix</code> 的所有坐标中第 <code>k</code> 大的值（<strong><code>k</code> 的值从 1 开始计数</strong>）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix = [[5,2],[1,6]], k = 1\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix = [[5,2],[1,6]], k = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix = [[5,2],[1,6]], k = 3\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix = [[5,2],[1,6]], k = 4\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= matrix[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= m * n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-kth-largest-xor-coordinate-value](https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-kth-largest-xor-coordinate-value](https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,2],[1,6]]\\n1', '[[5,2],[1,6]]\\n2', '[[5,2],[1,6]]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # presum[i][j] = presum[i-1][j] ^ presum[i][j-1] ^ presum[i-1][j-1] ^ matrix[i-1][j-1]\n",
    "        # topk -> 大根堆\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        presum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        queue = []\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                presum[i][j] = presum[i-1][j] ^ presum[i][j-1] ^ presum[i-1][j-1] ^ matrix[i-1][j-1]\n",
    "                if len(queue) < k:\n",
    "                    heapq.heappush(queue, presum[i][j])\n",
    "                elif presum[i][j] > queue[0]:\n",
    "                    heapq.heapreplace(queue, presum[i][j])\n",
    "        return queue[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ret = []\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            xor = 0\n",
    "            for j in range(n):\n",
    "                xor ^= matrix[i][j]\n",
    "                tmp = matrix[i][j] = (matrix[i - 1][j] if i > 0 else 0) ^ xor\n",
    "        \n",
    "                ret.append(tmp)\n",
    "        ret.sort()\n",
    "        # print(ret)\n",
    "        return ret[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n,m=len(matrix),len(matrix[0])\n",
    "        prefix=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                prefix[i+1][j+1]=prefix[i+1][j]^prefix[i][j+1]^prefix[i][j]^matrix[i][j]\n",
    "\n",
    "        minheap=[]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                heappush(minheap,prefix[i+1][j+1])\n",
    "                if len(minheap)>k: heappop(minheap)\n",
    "        return minheap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        heap = list()\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i-1][j] ^ dp[i][j-1] ^ dp[i-1][j-1] ^ matrix[i-1][j-1]\n",
    "                if len(heap) < k:\n",
    "                    heappush(heap, dp[i][j])\n",
    "                else:\n",
    "                    heappushpop(heap, dp[i][j])\n",
    "        return heap[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = matrix[0][0]\n",
    "\n",
    "        lst = [dp[0][0]]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i - 1][0] ^ matrix[i][0]\n",
    "            lst.append(dp[i][0])\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] ^ matrix[0][j]\n",
    "            lst.append(dp[0][j])\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i][j]\n",
    "                lst.append(dp[i][j])\n",
    "\n",
    "        lst.sort(reverse=True)\n",
    "\n",
    "        return lst[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Topk(object):\n",
    "    def __init__(self,k:int)->None:\n",
    "        self.k=k\n",
    "        self.data=[]\n",
    "        \n",
    "    def push(self,elem:int)->None:\n",
    "        if len(self.data)<self.k:\n",
    "            heapq.heappush(self.data,elem)\n",
    "        else:\n",
    "            top_small=self.data[0]\n",
    "            if elem>top_small:\n",
    "                heapq.heapreplace(self.data,elem)\n",
    "        \n",
    "    def numk(self)->int:\n",
    "        return self.data[0]\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        ans=Topk(k)\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=dp[i-1][j-1]^dp[i-1][j]^dp[i][j-1]^matrix[i-1][j-1]\n",
    "                ans.push(dp[i][j])\n",
    "        return ans.numk()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        queue = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        presum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                presum[i][j] = presum[i-1][j-1] ^ presum[i][j-1] ^ presum[i-1][j] ^ matrix[i-1][j-1]\n",
    "                if len(queue) < k:\n",
    "                    heapq.heappush(queue, presum[i][j])\n",
    "                elif presum[i][j] > queue[0]:\n",
    "                    heapq.heapreplace(queue, presum[i][j])\n",
    "        return queue[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        res = []\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                res.append(pre[i][j])\n",
    "\n",
    "        res.sort(reverse=True)\n",
    "        return res[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        lastrow = None\n",
    "        queue = []\n",
    "        cache = [0] * n\n",
    "        for i in range(m):\n",
    "            lastcol = None\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0:\n",
    "                    rs = matrix[i][j]\n",
    "                    lastrow = rs\n",
    "                    lastcol = rs\n",
    "                elif j==0:\n",
    "                    rs = lastrow ^ matrix[i][j]\n",
    "                    lastrow = rs\n",
    "                    lastcol = rs\n",
    "                else:\n",
    "                    cache[j] = cache[j] ^ matrix[i][j]\n",
    "                    rs = lastcol ^ cache[j]\n",
    "                    lastcol = rs\n",
    "                # print(i,j,rs)\n",
    "                if len(queue) < k:\n",
    "                    heapq.heappush(queue,rs)\n",
    "                elif rs > queue[0]:\n",
    "                    heapq.heappop(queue)\n",
    "                    heapq.heappush(queue,rs)\n",
    "                # print(queue)\n",
    "        return queue[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        t=matrix[0][0]\n",
    "        dp[0][0]=matrix[0][0]\n",
    "        q=[matrix[0][0]]\n",
    "        for i in range(1,m):\n",
    "            t^=matrix[i][0]\n",
    "            dp[i][0]=t \n",
    "            q.append(dp[i][0])\n",
    "        t=matrix[0][0]\n",
    "        for i in range(1,n):\n",
    "            t^=matrix[0][i]\n",
    "            dp[0][i]=t\n",
    "            q.append(dp[0][i])\n",
    "       # print(q)\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "               # print('loop',dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "                dp[i][j]=(dp[i-1][j]^dp[i][j-1]^dp[i-1][j-1]^matrix[i][j])\n",
    "                q.append(dp[i][j])\n",
    "        q.sort()\n",
    "      #  print(q)\n",
    "        return q[-k]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        tmp = list()\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0 and j - 1 >= 0:\n",
    "                    matrix[i][j] ^= matrix[i-1][j-1]\n",
    "                if i - 1 >= 0:\n",
    "                    matrix[i][j] ^= matrix[i-1][j]\n",
    "                if j - 1 >= 0:\n",
    "                    matrix[i][j] ^= matrix[i][j-1]\n",
    "                tmp.append(matrix[i][j])\n",
    "        # print(5 ^ 7 ^ 4 ^ 6)\n",
    "        # print(matrix)\n",
    "        # print(sorted(tmp))\n",
    "        return sorted(tmp, reverse=True)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        hp = []\n",
    "        for a in range(m):\n",
    "            for b in range(n):\n",
    "                if 0<=a-1: matrix[a][b] ^= matrix[a-1][b]\n",
    "                if 0<=b-1: matrix[a][b] ^= matrix[a][b-1]\n",
    "                if 0<=a-1 and 0<=b-1: matrix[a][b] ^= matrix[a-1][b-1]\n",
    "\n",
    "                hp.append(matrix[a][b])\n",
    "\n",
    "        hp.sort(reverse=True)\n",
    "\n",
    "        return hp[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        results = []\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                results.append(pre[i][j])\n",
    "\n",
    "        results.sort(reverse=True)\n",
    "        return results[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        res = []\n",
    "\n",
    "        arr = [0] * len(matrix[0])\n",
    "        for i in range(len(matrix)):\n",
    "            tmp = 0\n",
    "            for j in range(len(matrix[i])):\n",
    "                tmp ^= matrix[i][j]\n",
    "                arr[j] ^= tmp\n",
    "                res.append(arr[j])\n",
    "        \n",
    "        res.sort()\n",
    "        return res[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        hp = []\n",
    "        for a in range(1, m+1):\n",
    "            for b in range(1, n+1):\n",
    "                pre[a][b] = pre[a][b-1] ^ pre[a-1][b] ^ pre[a-1][b-1] ^ matrix[a-1][b-1]\n",
    "                if len(hp)<k: \n",
    "                    heapq.heappush(hp, pre[a][b])\n",
    "                else:\n",
    "                    heapq.heappush(hp, pre[a][b])\n",
    "                    heapq.heappop(hp)\n",
    "\n",
    "        \n",
    "        return hp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # 动态规划，加上加左减左上\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        # 预处理第一行与第一列\n",
    "        for i in range(1, m):\n",
    "            matrix[i][0] ^= matrix[i-1][0]\n",
    "        for i in range(1, n):\n",
    "            matrix[0][i] ^= matrix[0][i-1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                matrix[i][j] ^= matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i-1][j-1]\n",
    "        \n",
    "        return sorted(chain.from_iterable(matrix))[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        res=[]\n",
    "        arr=[0]*len(matrix[0])\n",
    "        for i in range(len(matrix)):\n",
    "            tmp=0\n",
    "            for j in range(len(matrix[i])):\n",
    "                tmp^=matrix[i][j]\n",
    "                arr[j]^=tmp\n",
    "                res.append(arr[j])\n",
    "        res.sort()\n",
    "        return res[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ x\n",
    "\n",
    "        def check(num: int) -> bool:\n",
    "            cnt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    if s[i][j] > num:\n",
    "                        cnt += 1\n",
    "            return cnt < k\n",
    "\n",
    "        l, r = 0, max(max(r) for r in s)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans=[]\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        s=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i+1][j+1]=s[i+1][j]^s[i][j+1]^s[i][j]^matrix[i][j]\n",
    "                ans.append(s[i+1][j+1])\n",
    "        ans.sort()\n",
    "        return ans[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        res = []\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                res.append(pre[i][j])\n",
    "\n",
    "        res.sort(reverse=True)\n",
    "        return res[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = []\n",
    "        pre = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ matrix[i-1][j-1]\n",
    "                ans.append(pre[i][j])\n",
    "        \n",
    "        ans.sort()\n",
    "        return ans[len(ans) - k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "\n",
    "        m, n = len(matrix) , len(matrix[0])\n",
    "\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        ret = []\n",
    "\n",
    "        for i in range(1, m + 1): \n",
    "\n",
    "            for j in range(1, n + 1): \n",
    "\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "\n",
    "                ret.append(pre[i][j])\n",
    "        \n",
    "        ret.sort(reverse = True )\n",
    "\n",
    "        return ret[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        hp = []\n",
    "        for a in range(m):\n",
    "            for b in range(n):\n",
    "                if 0<=a-1: matrix[a][b] ^= matrix[a-1][b]\n",
    "                if 0<=b-1: matrix[a][b] ^= matrix[a][b-1]\n",
    "                if 0<=a-1 and 0<=b-1: matrix[a][b] ^= matrix[a-1][b-1]\n",
    "                # print(\"[{},{}]={}\".format(a,b,matrix[a][b]))\n",
    "                if len(hp)<k: heapq.heappush(hp, matrix[a][b])\n",
    "                else:\n",
    "                    heapq.heappush(hp, matrix[a][b])\n",
    "                    heapq.heappop(hp)\n",
    "        # klargest = heapq.nlargest(k, hp)\n",
    "        # heapq.heapify(klargest)\n",
    "        \n",
    "        return hp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        hp = []\n",
    "        for a in range(1, m+1):\n",
    "            for b in range(1, n+1):\n",
    "                pre[a][b] = pre[a][b-1] ^ pre[a-1][b] ^ pre[a-1][b-1] ^ matrix[a-1][b-1]\n",
    "                hp.append(pre[a][b])\n",
    "        hp.sort(reverse=True)\n",
    "            \n",
    "        return hp[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        heap = list()\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i-1][j] ^ dp[i][j-1] ^ dp[i-1][j-1] ^ matrix[i-1][j-1]\n",
    "                # if len(heap) < k:\n",
    "                #     heappush(heap, dp[i][j])\n",
    "                # else:\n",
    "                #     heappushpop(heap, dp[i][j])\n",
    "                heap.append(dp[i][j])\n",
    "        heap.sort(reverse=True)\n",
    "        return heap[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        prefix = [[0] * n for _ in range(m)]\n",
    "        result = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 判断边界，如果超出边界则将该值设置为0\n",
    "                up = prefix[i-1][j] if i > 0 else 0\n",
    "                left = prefix[i][j-1] if j > 0 else 0\n",
    "                up_left = prefix[i-1][j-1] if i > 0 and j > 0 else 0\n",
    "                \n",
    "                prefix[i][j] = up ^ left ^ up_left ^ matrix[i][j]\n",
    "                result.append(prefix[i][j])\n",
    "\n",
    "        # 对所有异或的结果进行排序\n",
    "        result.sort(reverse=True)\n",
    "        \n",
    "        # 返回第 k 大的值\n",
    "        return result[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PreSum2d:\n",
    "    '''\n",
    "    二维前缀和（支持加法和异或）\n",
    "    '''\n",
    "\n",
    "    def __init__(self, grid, op=0):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.op = op\n",
    "        self.p = p = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        if op == 0:\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    p[i + 1][j + 1] = p[i][j + 1] + \\\n",
    "                        p[i + 1][j] - p[i][j] + grid[i][j]\n",
    "        elif op == 1:\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    p[i + 1][j + 1] = p[i][j + 1] ^ p[i + 1][j] ^ p[i][j] ^ grid[i][j]\n",
    "\n",
    "    def query(self, r1, c1, r2, c2):\n",
    "        '''\n",
    "        查询矩形 grid[r1: r2 + 1, c1: c2 + 1] 的值\n",
    "        '''\n",
    "        if self.op == 0:\n",
    "            return self.p[r2 + 1][c2 + 1] + self.p[r1][c1] - self.p[r1][c2 + 1] - self.p[r2 + 1][c1]\n",
    "        elif self.op == 1:\n",
    "            return self.p[r2 + 1][c2 + 1] ^ self.p[r1][c1] ^ self.p[r1][c2 + 1] ^ self.p[r2 + 1][c1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ps = PreSum2d(matrix, 1)\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nums.append(ps.query(0, 0, i, j))\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        return nums[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        nums = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                nums.append(dp[i][j])\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        xor_matrix = [[0] * m for _ in range(n)]\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                num = matrix[i][j]\n",
    "                if i > 0:\n",
    "                    num ^= xor_matrix[i - 1][j]\n",
    "                if j > 0:\n",
    "                    num ^= xor_matrix[i][j - 1]\n",
    "                if i > 0 and j > 0:\n",
    "                    num ^= xor_matrix[i - 1][j - 1]\n",
    "\n",
    "                xor_matrix[i][j] = num\n",
    "                ans.append(num)\n",
    "        return sorted(ans)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ans = []\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                ans.append(pre[i][j])\n",
    "\n",
    "        return sorted(ans)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ret = []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        dp = [[0]*m for _ in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0 and j == 0: dp[i][j] = matrix[i][j]\n",
    "                elif i == 0: dp[i][j] = matrix[i][j]^dp[i][j-1]\n",
    "                elif j == 0: dp[i][j] = matrix[i][j]^dp[i-1][j]\n",
    "                else: dp[i][j] = matrix[i][j]^dp[i-1][j]^dp[i][j-1]^dp[i-1][j-1]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ret.append(dp[i][j])\n",
    "        ret = sorted(ret, reverse=True)\n",
    "        return ret[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        pre=[[0]*(n+1) for _ in range(m+1)]\n",
    "        res=[]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                pre[i][j]=pre[i-1][j]^pre[i][j-1]^pre[i-1][j-1]^matrix[i-1][j-1]\n",
    "                res.append(pre[i][j])\n",
    "        return sorted(res,reverse=True)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # 凡是找出第k大/小的值，都用堆来找\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                 f[i][j] = f[i - 1][j - 1] ^ f[i - 1][j] ^ f[i][j - 1] ^ matrix[i - 1][j - 1]\n",
    "        return sorted([i for j in f[1:] for i in j], reverse=True)[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        #二维异或前缀和+排序\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        pre=[[0]*(n+1) for _ in range(m+1)]\n",
    "        res=[]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                pre[i][j]=pre[i-1][j]^pre[i][j-1]^pre[i-1][j-1]^matrix[i-1][j-1]\n",
    "                res.append(pre[i][j])\n",
    "        return sorted(res,reverse=True)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        prexor = [[0] for  _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prexor[i].append(prexor[i][-1] ^ matrix[i][j])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(i == 0):\n",
    "                    dp[i][j] = prexor[i][j+1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] ^ prexor[i][j+1]\n",
    "                nums.append(dp[i][j])\n",
    "        nums.sort(reverse = True)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        xorMat = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        xorRes = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                xorMat[i+1][j+1] = xorMat[i+1][j] ^ xorMat[i][j+1] ^ xorMat[i][j] ^ matrix[i][j]\n",
    "                xorRes[i * n + j] = xorMat[i+1][j+1]\n",
    "        return sorted(xorRes)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        prexor = [[0] for  _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prexor[i].append(prexor[i][-1] ^ matrix[i][j])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(i == 0):\n",
    "                    dp[i][j] = prexor[i][j+1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] ^ prexor[i][j+1]\n",
    "                nums.append(dp[i][j])\n",
    "        nums.sort(reverse = True)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        prexor = [[0] for  _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prexor[i].append(prexor[i][-1] ^ matrix[i][j])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(i == 0):\n",
    "                    dp[i][j] = prexor[i][j+1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] ^ prexor[i][j+1]\n",
    "                nums.append(dp[i][j])\n",
    "        nums.sort(reverse = True)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        results = list()\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                results.append(pre[i][j])\n",
    "        \n",
    "        def nth_element(left: int, kth: int, right: int, op: Callable[[int, int], bool]):\n",
    "            if left == right:\n",
    "                return\n",
    "            \n",
    "            pivot = random.randint(left, right)\n",
    "            results[pivot], results[right] = results[right], results[pivot]\n",
    "\n",
    "            # 三路划分（three-way partition）\n",
    "            sepl = sepr = left - 1\n",
    "            for i in range(left, right + 1):\n",
    "                if op(results[i], results[right]):\n",
    "                    sepr += 1\n",
    "                    if sepr != i:\n",
    "                        results[sepr], results[i] = results[i], results[sepr]\n",
    "                    sepl += 1\n",
    "                    if sepl != sepr:\n",
    "                        results[sepl], results[sepr] = results[sepr], results[sepl]\n",
    "                elif results[i] == results[right]:\n",
    "                    sepr += 1\n",
    "                    if sepr != i:\n",
    "                        results[sepr], results[i] = results[i], results[sepr]\n",
    "            \n",
    "            if sepl < left + kth <= sepr:\n",
    "                return\n",
    "            elif left + kth <= sepl:\n",
    "                nth_element(left, kth, sepl, op)\n",
    "            else:\n",
    "                nth_element(sepr + 1, kth - (sepr - left + 1), right, op)\n",
    "\n",
    "        nth_element(0, k - 1, len(results) - 1, operator.gt)\n",
    "        return results[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        results = list()\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]\n",
    "                results.append(pre[i][j])\n",
    "        \n",
    "        def nth_element(left: int, kth: int, right: int, op: Callable[[int, int], bool]):\n",
    "            if left == right:\n",
    "                return\n",
    "            \n",
    "            pivot = random.randint(left, right)\n",
    "            results[pivot], results[right] = results[right], results[pivot]\n",
    "\n",
    "            # 三路划分（three-way partition）\n",
    "            sepl = sepr = left - 1\n",
    "            for i in range(left, right + 1):\n",
    "                if op(results[i], results[right]):\n",
    "                    sepr += 1\n",
    "                    if sepr != i:\n",
    "                        results[sepr], results[i] = results[i], results[sepr]\n",
    "                    sepl += 1\n",
    "                    if sepl != sepr:\n",
    "                        results[sepl], results[sepr] = results[sepr], results[sepl]\n",
    "                elif results[i] == results[right]:\n",
    "                    sepr += 1\n",
    "                    if sepr != i:\n",
    "                        results[sepr], results[i] = results[i], results[sepr]\n",
    "            \n",
    "            if sepl < left + kth <= sepr:\n",
    "                return\n",
    "            elif left + kth <= sepl:\n",
    "                nth_element(left, kth, sepl, op)\n",
    "            else:\n",
    "                nth_element(sepr + 1, kth - (sepr - left + 1), right, op)\n",
    "\n",
    "        nth_element(0, k - 1, len(results) - 1, operator.gt)\n",
    "        return results[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        x = [[0]*(col+1) for i in range(row+1)]\n",
    "        \n",
    "        q = []\n",
    "        for i in range(1,row+1):\n",
    "            for j  in range(1,col+1):\n",
    "                \n",
    "                \n",
    "                x[i][j] =x[i-1][j-1]^x[i][j-1]^x[i-1][j]^matrix[i-1][j-1]\n",
    "                heapq.heappush(q,-x[i][j])\n",
    "        print(q)\n",
    "        while k:\n",
    "            b= heapq.heappop(q)\n",
    "            k-=1\n",
    "            \n",
    "                \n",
    "        return -b"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
